The invention relates generally to the field of digital computer systems, and more particularly to systems and methods for facilitating the synchronization of access to variables and other resources which may be shared among a plurality of threads of execution in a digital computer system.
Computers process programs in one or more threads. In a computer having a plurality of processors, a plurality of threads can be executed in parallel, with each processor executing a thread. If there are more threads than the number of processors, at least one of the processors will execute a plurality of threads generally in an interleaved basis in a plurality of successive time slots. In a uni-processor computer, that is, a computer having a single processor, the processor will also execute the threads generally in an interleaved basis in a plurality of time slots.
Typically in multi-threaded programs, a thread will use a mutual exclusion mechanisms to avoid interference from and data race conditions with other threads. As an example of the utility of a mutual exclusion mechanism, consider code along the lines of Code Segment 1, which depicts code for a thread comprising a routine xe2x80x9cgetTicketxe2x80x9d in which the value of a variable xe2x80x9cTicketxe2x80x9d is incremented:
In Code Segment 1, the code is illustratively in the SPARC instruction set (reference SPARC International, Inc [David L. Weaver and Tom Germond (eds)], The SPARC Architecture Manual Version 9 (Prentice-Hall, 1994)).
In Code Segment 1, the getTicket routine includes a xe2x80x9ccritical sectionxe2x80x9d comprising lines (7) through (9) which are to be executed as an atomic xe2x80x9cread-modify-writexe2x80x9d operation to enable the value of the variable xe2x80x9cTicketxe2x80x9d to be incremented. To ensure that the operation is performed in an atomic manner, without variable xe2x80x9cTicketxe2x80x9d being accessed by another thread before the one thread has finished executing the critical section, the getTicket routine makes use of a xe2x80x9cmutexxe2x80x9d (xe2x80x9cmutual exclusionxe2x80x9d) mechanism to synchronize access to the variable xe2x80x9cTicket.xe2x80x9d The mutual exclusion mechanism ensures that, while the thread which includes the getTicket routine is executing the routine, only that thread will be able to access and perform operations in connection with the variable Ticket. In particular, line (5) (xe2x80x9ccall mutex-enterxe2x80x9d) initiates the synchronization and line (10) (xe2x80x9ccall mutex_exitxe2x80x9d) terminates synchronization. The code in both of these lines represent calls to the operating system, which locks the variable xe2x80x9cTicketxe2x80x9d for the thread which includes the getTicket routine in response to the mutex_enter call, and unlocks the variable xe2x80x9cTicket,xe2x80x9d making it available to other threads, in response to the mutex_exit call. After the variable xe2x80x9cTicketxe2x80x9d has been locked in response to the mutex_enter call, and before the variable xe2x80x9cTicketxe2x80x9d is unlocked in response to the mutex_exit call, the getTicket routine enables the variable xe2x80x9cTicketxe2x80x9d to be retrieved from the computer""s memory and loaded into one of the processor""s internal registers (line 7), incremented (line 8) and stored back into the computer""s memory (line (9)).
The benefit of the synchronization will be clear from the following. If, for example, the thread""s time slot ends after the variable xe2x80x9cTicketxe2x80x9d has been retrieved from the memory and loaded into an internal register, and before the value as incremented by the getTicket routine has been stored in the memory, another thread retrieves the variable xe2x80x9cTicket,xe2x80x9d increments its value by some amount and stores the value as incremented by that thread in the memory, when the thread (that is, the thread executing the getTicket routine) stores the value as incremented by it in the memory, it will over-write the value as stored by the other thread. Accordingly, the value of the variable xe2x80x9cTicketxe2x80x9d as retrieved by the other thread will correspond to the original, non-incremented value, instead of the incremented value which presumably was the value that the other thread was to have processed. More important, however, is that, since the thread that is executing the getTicket routine has over-written the value as stored by the other thread, the value as processed by the other thread will not be reflected in subsequent processing operations. However, by synchronizing access to the variable xe2x80x9cTicket,xe2x80x9d the thread which executes the getTicket routine can forbid the other thread from accessing the variable xe2x80x9cTicketxe2x80x9d until after the value has been retrieved, incremented and stored in the memory, even if those operations occur in different time slots. This may delay operations by the other thread, since the other thread will need to wait until after the thread that is executing the getTicket routine has finished operating with the variable and ended synchronization, but it will ensure that the processing operations take place in the correct order.
However, use of synchronization primitives such as the xe2x80x9cmutex_enterxe2x80x9d and xe2x80x9cmutex_exitxe2x80x9d themselves incur some cost. Since the synchronization primitives require calls to the operating system kernel, they can result in relatively long processing times. U.S. patent application Ser. No. 09/174,278, filed Oct. 16, 1998, in the name of David Dice, et al., and entitled System And Method For Synchronizing Access To Shared Variables In A Virtual Machine In A Digital Computer System, and assigned to the assignee of the current convention, describes a wait-free synchronization arrangement for facilitating synchronization by enabling one thread to use a compare and swap instruction to detect when the value of a variable which may be accessed by multiple processes or threads has been changed by another thread while the one thread has been executing a critical section. While that arrangement can facilitate synchronization, it will be appreciated at one such compare and swap instruction will be used each variable requiring synchronization during execution of the critical section, and, if multiple variables require synchronization, then a corresponding number of compare and swap instruction will be used.
The invention provides a new and improved system and method for facilitating the synchronization of access to variables and other resources which may be shared among a plurality of threads of execution in a digital computer system.
In brief summary, the invention provides, in one embodiment, a mutual exclusion arrangement for use in connection with a computer. The computer is configured to execute at least one program having at least one thread in a series of time slots. The mutual exclusion arrangement includes, associated with the computer, a signal generator and, associated with the at least one thread, a signal handler. The signal generator is configured to generate a signal for provision to the at least one thread when the computer initiates processing of the at least one thread in one of the time slots. The signal handler is configured to, in response to the signal, determine whether the thread, when it begins execution in the time slot, will be executing a section of code that is to be executed in an atomic manner, and, if so, enable the thread to begin execution at a beginning of the section, and otherwise enable the thread to begin execution subsequent to previously-executed code.
The arrangement effectively provides a form of mutual exclusion, similar to that provided by the synchronization primitives such as mutex_enter and mutex_exit, for atomic operations associated with critical sections of a thread. However, instead of doing so in an active manner, by forbidding access to a variable by other threads in the manner accomplished by conventional synchronization primitives, the present arrangement essentially allows a thread which is executing a critical section which makes use of the variable to determine when an event has occurred which may make the variable accessible to other threads. A variable can be accessed by other threads if the time slot of the thread that includes the critical section terminates while the thread is executing the critical section. By notifying the thread, when it resumes execution, that execution of the thread has been pre-empted, the thread can thereafter perform whatever operations it deems necessary on the assumption that the variable in fact had been accessed. Thus, the invention provides an arrangement by which the thread can detect and recover from an event which can expose the variable to being processed by another thread, as distinguished from using conventional synchronization primitives, which require relatively lengthy calls to the operating system to ensure that another thread will not access.
In addition, the arrangement does not require the use of compare-and-swap instructions, which provide fine-grained synchronization for each of the variables which may be used in a critical section.